690. 员工的重要性

Similar Question

leading to the advanced question

Solution Tips

方案一: 哈希表 + BFS

var GetImportance = function(employees, id) {
    console.log('employees: ', employees);
    // 首先要找到 id, 然后要遍历所有的子孙后代
    // 这题和层次遍历的关系是什么呢? 找 id 找起来会快一点?
    // 就用层次遍历来做吧, 之前递归的写过好多了

    // employees 是普通对象, 难道要先转换成树形的结构?
    // 转换成哈希表跟好呀, 反正 id 不可能重复的, 第一轮遍历转换成哈希表, 顺表找到 id 即可
    const map = {};
    let target;
    for (let i = 0; i < employees.length; i++) {
        const item = employees[i];
        map[item.id] = item;
        if (item.id === id) {
            target = item;
        }
    }

    // 计算 importance
    let sum = 0;
    const queue = [map[target]];

    while (queue.length) {
        const item = queue.pop();
        sum += item.importance;

        for (let i = 0; i < item.subordinates.length; i++) {
            const id = item.subordinates[i];
            queue.push(map[id])
        }
    }

    return sum;
};